package com.csw.shuanfa.SuanFa;

/**
 * 一个数组里面是版本号
 * 用最短的办法，查询出错误低版本号是哪一个，提示二分
 */
public class TestErFen {

    public static void main(String[] args) {

        // String[] versions = new String[]{"1", "2", "3", "wrong1", "wrong2"};
        // String[] versions = new String[]{ "wrong1", "wrong2"};
        // String[] versions = new String[]{"1", "2", "3", "4", "wrong1", "wrong2"};/
        String[] versions = new String[]{"a0", "a0", "a0", "a0", "a0", "wrong1", "wrong2", "wrong3", "wrong4"};
        /**
         *hash10  wrong2qweqweqwe5 qoweioqhw32
         * doadjadj43 wrong2qweqweqwe5 wrong1ashdauhdu4
         * doadjadj43 doadjadj43 doadjadj43
         */
        //findFirstWrong(versions));
    }


    /**
     * Return The first version of code that contains bugs and is wrong.
     *
     * @param versions total version of codes that are order by commit time.
     * @return The first wrong version of code.
     */
    public static String findFirstWrong(String[] versions) {
        int str = 0;
        int end = versions.length - 1;
        int me = (str + end) / 2;
        String med = versions[me];
        int res = change(versions, str, end, me, 0, false);
        return versions[res];
    }

    private static int change(String[] versions, int str, int end, int me, int index, boolean isTrue) {

        if (checkRight(versions[me]) == true) {//在左边
            if (str == end) {
                return me;
            }
            int aa = me;
            end = me - 1;
            me = (str + end) / 2;
            if (str <= end) {
                int res = change(versions, str, end, me, aa, true);
                return res;
            }
        } else {//在右边
            if (str == end) {
                return index;
            }
            str = me + 1;
            me = (str + end) / 2;
            if (str <= end) {
                int res = change(versions, str, end, me, index, false);
                return res;
            }
        }
        return -1;

    }

    /**
     * Check code which is right and contains no bugs.
     *
     * @param version The hash of code from one commit.
     * @return True if the version of code is Right. Otherwise return False.
     */
    public static boolean checkRight(String version) {

        // Just mock some time consuming check
        // doSomeTimeConsumingCheck();

        if (version.startsWith("wrong")) {
            return true;
        } else {
            return false;
        }
    }

    public static void doSomeTimeConsumingCheck() {
        try {
            Thread.sleep(1000L);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }

}
